package first.codeTop.byteDance;


import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName LC113
 * @description:
 * @author: 荣燊
 * @create: 2021-10-20 16:57
 **/
public class LC113 {
    // 路径总和II
    static List<List<Integer>> ans = new ArrayList<>();
    static List<Integer> ansSon = new ArrayList<>();

    public static List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum);
        return ans;
    }

    public static void dfs(TreeNode root, int targetSum) {
        if (root == null) {
            return;
        }
        ansSon.add(root.val);
        targetSum -= root.val;
        if (root.left == null && root.right == null && targetSum == 0) {
            ans.add(new ArrayList<>(ansSon));
        }
        dfs(root.left, targetSum);
        dfs(root.right, targetSum);
        ansSon.remove(ansSon.size()-1);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        System.out.println(pathSum(root, 3));
    }
}
